#pragma once

#include <thrust/binary_search.h>
#include <thrust/sort.h>

// TODO scalar search funtions (lower_bound, upper_bound, binary_search, equal_range)

template <typename Container1,
          typename Container2,
          typename Container3>
struct LowerBound
{
  Container1 A; // haystack
  Container2 B; // needles
  Container3 C; // positions

  template <typename Range1, typename Range2, typename Range3>
  LowerBound(const Range1& X, const Range2& Y, const Range3& Z)
    : A(X.begin(), X.end()),
      B(Y.begin(), Y.end()),
      C(Z.begin(), Z.end())
  {
    thrust::stable_sort(A.begin(), A.end());
  }

  void operator()(void)
  {
    thrust::lower_bound(A.begin(), A.end(), B.begin(), B.end(), C.begin());
  }
  
  void reset(void)
  {
    // nothing to do
  }
};

template <typename Container1,
          typename Container2,
          typename Container3,
          typename Compare>
struct LowerBoundComp
{
  Container1 A; // haystack
  Container2 B; // needles
  Container3 C; // positions
  Compare comp;

  template <typename Range1, typename Range2, typename Range3>
  LowerBoundComp(const Range1& X, const Range2& Y, const Range3& Z, Compare comp)
    : A(X.begin(), X.end()),
      B(Y.begin(), Y.end()),
      C(Z.begin(), Z.end()),
      comp(comp)
  {
    thrust::stable_sort(A.begin(), A.end(), comp);  
  }

  void operator()(void)
  {
    thrust::lower_bound(A.begin(), A.end(), B.begin(), B.end(), C.begin(), comp);
  }
  
  void reset(void)
  {
    // nothing to do
  }
};

template <typename Container1,
          typename Container2,
          typename Container3>
struct UpperBound
{
  Container1 A; // haystack
  Container2 B; // needles
  Container3 C; // positions

  template <typename Range1, typename Range2, typename Range3>
  UpperBound(const Range1& X, const Range2& Y, const Range3& Z)
    : A(X.begin(), X.end()),
      B(Y.begin(), Y.end()),
      C(Z.begin(), Z.end())
  {
    thrust::stable_sort(A.begin(), A.end());
  }

  void operator()(void)
  {
    thrust::upper_bound(A.begin(), A.end(), B.begin(), B.end(), C.begin());
  }

  void reset(void)
  {
    // nothing to do
  }
};

template <typename Container1,
          typename Container2,
          typename Container3,
          typename Compare>
struct UpperBoundComp
{
  Container1 A; // haystack
  Container2 B; // needles
  Container3 C; // positions
  Compare comp;

  template <typename Range1, typename Range2, typename Range3>
  UpperBoundComp(const Range1& X, const Range2& Y, const Range3& Z, Compare comp)
    : A(X.begin(), X.end()),
      B(Y.begin(), Y.end()),
      C(Z.begin(), Z.end()),
      comp(comp)
  {
    thrust::stable_sort(A.begin(), A.end(), comp);  
  }

  void operator()(void)
  {
    thrust::upper_bound(A.begin(), A.end(), B.begin(), B.end(), C.begin(), comp);
  }

  void reset(void)
  {
    // nothing to do
  }
};


template <typename Container1,
          typename Container2,
          typename Container3>
struct BinarySearch
{
  Container1 A; // haystack
  Container2 B; // needles
  Container3 C; // booleans

  template <typename Range1, typename Range2, typename Range3>
  BinarySearch(const Range1& X, const Range2& Y, const Range3& Z)
    : A(X.begin(), X.end()),
      B(Y.begin(), Y.end()),
      C(Z.begin(), Z.end())
  {
    thrust::stable_sort(A.begin(), A.end());
  }

  void operator()(void)
  {
    thrust::binary_search(A.begin(), A.end(), B.begin(), B.end(), C.begin());
  }

  void reset(void)
  {
    // nothing to do
  }
};

template <typename Container1,
          typename Container2,
          typename Container3,
          typename Compare>
struct BinarySearchComp
{
  Container1 A; // haystack
  Container2 B; // needles
  Container3 C; // booleans
  Compare comp;

  template <typename Range1, typename Range2, typename Range3>
  BinarySearchComp(const Range1& X, const Range2& Y, const Range3& Z, Compare comp)
    : A(X.begin(), X.end()),
      B(Y.begin(), Y.end()),
      C(Z.begin(), Z.end()),
      comp(comp)
  {
    thrust::stable_sort(A.begin(), A.end(), comp);  
  }

  void operator()(void)
  {
    thrust::binary_search(A.begin(), A.end(), B.begin(), B.end(), C.begin(), comp);
  }

  void reset(void)
  {
    // nothing to do
  }
};

